class Solution {
    public int superEggDrop(int k, int n) {
        int[][] dp = new int[n + 1][k + 1];

        // 分为蛋碎和没碎
        for (int i = 1; ; i++) {
            for (int j = 1; j <= k; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] + 1;
            }
            if (dp[i][k] >= n) return i;
        }
    }
}